The present invention relates generally to global navigation satellite systems, and more particularly to selection of a subset of global navigation satellite system measurements.
Global navigation satellite systems (GNSSs) enable determination of target parameters, such as position, velocity, and time (PVT) for users equipped with receivers of GNSS signals. Currently deployed global navigation satellite systems are the United States Global Positioning System (GPS) and the Russian GLONASS. Other global navigation satellite systems, such as the European GALILEO system, are under development. In a GNSS, a navigation receiver receives and processes radio signals transmitted by satellites located within a line-of-sight of the receiver. The satellite signals comprise carrier signals modulated by pseudo-random binary codes. The receiver measures the time delays of the received signals relative to a local reference clock or oscillator. Code phase measurements enable the receiver to determine the pseudo-ranges between the receiver and the satellites. The pseudo-ranges differ from the actual ranges (distances) between the receiver and the satellites due to an offset between the time scales of the GNSS and the receiver. If signals are received from a sufficiently large number of satellites, then the measured pseudo-ranges can be processed to determine the coordinates and the offset between the time scales of the GNSS and the receiver. This operational mode is referred to as a stand-alone mode, since the measurements are determined by a single receiver. A stand-alone system typically provides meter-level accuracy of positioning.
To improve the accuracy of positioning, differential navigation (DN) systems have been developed. In a DN system, the position of a user is determined relative to a base station, also referred to as a base. The base is typically fixed, and the coordinates of the base are precisely known; for example, by surveying. The base contains a navigation receiver that receives satellite signals and that can determine the corrections to GNSS measurements based on the known base position. In some DN systems, the raw measurements of the base can serve as corrections.
The user, whose position is to be determined, can be stationary or mobile; in a DN system, the user is often referred to as a rover. The rover also contains a navigation receiver that receives GNSS satellite signals. Corrections generated at the base are transmitted to the rover via a communications link. To accommodate a mobile rover, the communications link is often a wireless link. The rover processes the corrections received from the base, along with measurements taken with its own receiver, to improve the accuracy of determining its position. Accuracy is improved in the differential navigation mode because errors incurred by the receiver at the rover and by the receiver at the base are highly correlated. Since the coordinates of the base are accurately known, measurements from the base can be used for calculating corrections, thus compensating the errors at the rover. A DN system provides corrections to pseudo-ranges measured with code phase.
The position determination accuracy of a differential navigation system can be further improved if the pseudo-ranges measured with code phase are supplemented with the pseudo-ranges measured with carrier phase. If the carrier phases of the signals transmitted by the same satellite are measured by both the navigation receiver in the base and the navigation receiver in the rover, processing the two sets of carrier phase measurements can yield a position determination accuracy to within several percent of the carrier's wavelength. A differential navigation system that computes positions based on real-time carrier phase pseudo-range measurements, in addition to the code phase pseudo-range measurements, is often referred to as a real-time kinematic (RTK) system. Processing carrier phase measurements to determine coordinates includes the step of ambiguity resolution; that is, determining the integer number of cycles in these measurements acquired by the navigation receiver from an individual satellite.
Applications based on GNSSs have become increasingly popular as the number of available GNSS satellites has increased and as the cost of GNSS receivers has decreased. Measurements from a minimum of four satellites can determine three-dimensional position and time; however, measurements from additional satellites can be used to improve accuracy. Typically, more than four satellites are in view, and redundant measurements are available. Previous generations of receivers were not capable of tracking all the GNSS satellites in view due to hardware limitations; thus, a subset of the satellites in view had to be selected such that the subset provided the best performance, that is, the best accuracy of the PVT solution. This selection process was equivalent to selecting a subset of measurements from the set of available measurements.
The current generation of receivers do not have such hardware limitations; in addition, they can simultaneously process signals transmitted on different frequency bands (for example, both L1 and L2), and they can simultaneously process signals transmitted from different GNSSs (for example, from both GPS and GLONASS). As the capability to track more signals increases, however, the required computational power of the receiver increases. In general, increased computational power requires more complex hardware, higher power consumption, and higher cost. Selecting an optimum subset of measurements from all available measurements, therefore, is still advantageous for producing receivers with smaller size, lower power consumption, and lower cost.
The general problem addressed herein can then be formulated as follows. The total number of available measurements is N. Assume that, with given constraints of computational resources and computational time, only n measurements (where n is an integer, and n<N) are to be selected for computing target parameters within a specified accuracy. Examples of target parameters include position, velocity, and time. Which subset of n measurements selected from the set of available N measurements will yield the best accuracy for the target parameters? This subset is referred to as the optimum measurement subset for the target parameters.
Several approaches have been used to select the optimum measurement subset. One previous approach is based on analysis of the signal-to-noise ratio (SNR) or signal power. Assume that n measurements are to be selected out of N measurements. Under this approach, all satellite measurements are ranked in accordance with SNR or signal power values. Then, the n measurements with the highest SNR or signal power values are selected and used for further processing.
Another previous approach is based on analysis of satellite elevation angle. Measurements from low-elevation satellites are subject to multipath reflection, refraction, and attenuation arising from various signal obstacles and obstructions. In this approach, the measurements that come from satellites below a particular elevation threshold are rejected, and the measurements that come from satellites above the elevation threshold are retained for calculating positions, velocities, or time.
Approaches based on analysis of SNR, signal power, and elevation angle values have the advantage of requiring relatively low computer resources; however, they do not provide optimum accuracy of the PVT solution.
In contrast with the above approaches, analysis of Dilution of Precision (DOP) values provides selection of the measurements that produce the PVT solution with the best accuracy; however, the DOP approach requires substantially more computer resources. The DOP approach for selecting optimum measurements is summarized below.
The DOP approach is based on a general approach in accordance with the Least Squares Method (LSM). The measurement equation is expressed as:y=Hx,  (E1)
where:                y is a measurement vector;        X is a vector of unknowns; and        H is a design matrix that relates y and X.        
In accordance with the LSM, the vector of unknowns is determined as follows:x=(HTWH)−1HTWy.  (E2)Here W is a diagonal weight matrix:
                              W          =                      [                                                                                σ                    1                                          -                      2                                                                                        0                                                  …                                                  0                                                                              0                                                                      σ                    2                                          -                      2                                                                                        …                                                  0                                                                              …                                                  …                                                  …                                                  …                                                                              0                                                  0                                                  …                                                                      σ                    N                                          -                      2                                                                                            ]                          ,                            (        E3        )            
where:
σi are coefficients characterizing measurement errors of the i-th element in the y-vector; and
N is the total number of measurements.                The P matrix is introduced as follows:P=(HTWH)−1.  (E4)This P matrix is the solution covariance matrix; it can be used for evaluating solution accuracy based on the relationship between measured parameters, target parameters, and measurement weights. Then, the DOP value is denoted as:        
                              DOP          =                                                    ∑                                  i                  ∈                                      [                    L                    ]                                                              ⁢                              P                                  i                  ,                  i                                                                    ,                            (        E5        )            
where:
[L] is an index for the variables used; and
Pi,i is the diagonal element of the P matrix.
The weights in (E4) can be assigned in a variety of ways. In one method, User Ranging Accuracy (URA) and the satellite “health” information in the navigation data can be used (J. W. Lavrakis and C. Shank, “A Study into the Use of URA in Satellite Selection,” Proceedings of the 49th Annual Meeting of the Institute of Navigation, 1993). In a second method, modeled values of ionospheric and tropospheric delays based on the elevation angle can be applied (P. Chansik et al., “A satellite selection criterion incorporating the effect of elevation angle in GPS positioning”, Control Engineering Practice, vol. 4, 1996). In a third method, SNR (Y. Yang, et al, “GDOP results in all-in-view positioning and in four optimum satellites positioning with GPS PRN codes ranging”, Position Location and Navigation Symposium, Piscataway, N.J., USA: IEEE, 2004) or signal power (M. C. Moreau, “GPS receiver architecture for autonomous navigation in high earth orbits”, Colorado, United States: PhD Thesis, University of Colorado at Boulder, 2001) is used for assigning weights.
There is another commonly used approach for calculating DOP, developed earlier than (E4) above. It relates to a less general case in which all weights are equal to 1, or to a particular value that can be separated as a common factor; the P matrix then reduces to:P=(HTH)−1.  (E6)
Depending on the composition of the design matrix and the L index, the following metrics can be used for selecting optimum measurements: Geometrical DOP (GDOP), Position DOP (PDOP), Horizontal DOP (HDOP), Vertical DOP (VDOP), and Time DOP (TDOP). Other metrics can be used as well.
The criterion for measurement selection is based on the following relationship: as the DOP decreases, the accuracy of the PVT solution increases. Thus, n measurements are selected from N available measurements to yield the smallest DOP. This approach for selecting optimum measurements based on DOP analysis is referred to herein as the “classical” approach.
The main drawback of the classical approach is that substantial computational resources are required to compute DOP values for different combinations of measurements. For example, if there is a requirement to select 12 measurements out of 13 measurements, then 13 candidate combinations need to be tested; that number of combinations is generally acceptable. If there is a requirement to select 12 measurements out of 18 measurements, however, then 18,564 candidate combinations need to be tested. This number of combinations is too computationally intensive in practice; especially, if the selection is repeated once per epoch (for example, once per second).
To reduce the computational load, a combination of the three above methods can be applied (that is, selection based on elevation, SNR or signal power, and DOP). One approach to combine all three methods is described in France et al., “Selecting Raw Measurements for Use in Position Computation”, U.S. Patent Application Publication No. 2011/0057833. Since a DOP algorithm is still used as part of the overall method, however, the overall method still presents a substantial computational load.
There are additional approaches for selecting a measurement subset with a minimum DOP value. These approaches require fewer computational resources, but they are not reliable. The selected subsets sometimes do provide the minimum DOP value, but sometimes they do not. A popular satellite selection algorithm is called “Lear's simple satellite selection algorithm”; it is more widely known as the “Highest Elevation” algorithm [W. M. Lear, “Proposed Simplified GPS Navigation Filters”, Johnson Space Center Internal Note JSC-25468, February, 1992]. The highest satellite is first selected, and then satellites are added according to best-match criteria depending on azimuthal separation. The second selected satellite is 90° away from the first; the third selected satellite is perpendicular to the plane formed by the first two; the fourth and the fifth satellites are selected to minimize PDOP. This approach produces reasonably good results with a very small computational load, and it can be extended to selecting more than five satellites.
When selecting four satellites, the optimally selected satellites form a tetrahedron around the receiver. The volume of the tetrahedron is inversely proportional to the corresponding GDOP. Thus, by maximizing the volume, GDOP is minimized (M. Kihara and T. Okada, “A Satellite Selection Method and Accuracy for the Global Positioning System”, Journal of Navigation, vol. 31, pp. 8-20, 1984).
Numerous algorithms have been developed based on this approach; however, they are limited to selecting four satellites. An approach described by M. Zhang et al. (M. Zhang et al. “Satellite selection for multi-constellation”, Position Location and Navigation Symposium, Piscataway, N.J., USA, IEEE, 2008) accommodates additional satellites. Their approach allows selecting 5 to 16 satellites such that two to five satellites lie at zenith while others are uniformly distributed along the horizon circle. Their simulation results show an average of 5.79% GDOP increase compared with the results calculated with the optimal algorithm, and a 50% GDOP increase in a worst case.
Another approach that permits the selection of any desired number of satellites from those in view is based on the calculation of cost functions for every satellite (C. W. Park and J. P. How, “Quasi-Optimal Satellite Selection Algorithm for Real-Time Applications”, Proceedings of the 14th International Technical Meeting of the Satellite Division, ION GPS 2001, 2001, pp. 3018-3028). The cost functions for a particular satellite are calculated as sums of cosines of spatial separation angles between the particular satellite and other satellites. The satellites with minimum cost functions are selected.
Another approach is described in “A Recursive Quasi-optimal Fast Satellite Selection Method for GNSS Receivers” by Min Liu et al., Proceedings of the 22nd International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS 2009), Sep. 22-25, 2009, Savannah, Ga. This approach is based on estimating the DOP values, but, in order to save processing power, it is done sub-optimally. According to this approach, on the first step, each satellite is excluded one-by-one, while the others are retained, and the subset (first subset) with the smallest DOP is selected. On the second step, from the first subset, each satellite is excluded one-by-one, while the others are retained, and the new subset (second subset) with the smallest DOP is selected. The selection process is repeated until the desired number of satellites remain. To reduce processor load, calculation of DOP at each step is done iteratively, based on the results of the previous step.
What is needed is a method for selecting an optimum measurement subset that yields an accuracy for target parameters very close to or equal to the accuracy resulting from the optimum measurement subset determined by the dilution of precision analysis, but requires less computational resources or less computational time than the dilution of precision analysis.